package com.lili.dt;

import java.util.List;

/**
 * @Auther: 李 力
 * @Date: 2024/8/7
 * @Description: 贝尔曼-福特算法:求最短路劲
 * @version: 1.0
 */
public class BellmanFord {

    /*
        f(v) 用来表示从起点出发，到达 v 这个顶点的最短距离
        初始时
        f(v) = 0   当 v==起点 时
        f(v) = ∞   当 v!=起点 时

        之后
        新           旧     所有from
        f(to) = min(f(to), f(from) + from.weight)

        from 从哪来
        to   到哪去
 */
    //边类
    private static class Edge {
        public int from;
        public int to;
        public int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static int[] bellmanFord(List<Edge> edges, int n) {
        //一维数组:用来缓存结果，数组索引代表编号，元素代表从顶点到达该点的最短距离
        //数组长度就是顶点的个数，但是为了索引和顶点编号对应，数组长度加1，索引1后的是有效值
        int[] arr = new int[n + 1];
        arr[1] = 0;
        for (int i = 2; i < arr.length; i++) {
            //无穷大
            arr[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < n - 1; i++) {
            for (Edge edge : edges) {
                if (arr[edge.from] != Integer.MAX_VALUE) {
                    arr[edge.to] = Math.min(arr[edge.to], arr[edge.from] + edge.weight);
                }
            }
        }
        return arr;
    }
}
